//
// Created by Administrator on 2021/11/9.
// May Saint Diana bless you!
//

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int numTeams(vector<int> &rating) {
        unsigned int n = rating.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    if ((rating[k] > rating[j]) and (rating[j] > rating[i]) or
                                                    (rating[k] < rating[j]) and (rating[j] < rating[i]))
                        ++ans;
                }
            }
        }
        return ans;
        // 超时
    }

    int numTeams2(vector<int> &rating) {
        unsigned int n = rating.size();
        int  ans = 0;
        // 枚举中间的那个数
        // 统计左边更小的，右边更大的
        // 统计左边更大的，右边更小的
        for (int j = 0; j < n; ++j) {
            int leftLess = 0, leftMore = 0;
            int rightLess = 0, rightMore = 0;
            for (int i = 0; i < j; ++i) {
                if (rating[i] < rating[j])
                    ++leftLess;
                else if (rating[i] > rating[j])
                    ++leftMore;
            }
            for (int i = j + 1; i < n; ++i) {
                if (rating[i] > rating[j])
                    ++rightMore;
                else if (rating[i] < rating[j])
                    ++rightLess;
            }
            ans += leftLess * rightMore;
            ans += leftMore * rightLess;
        }
        return ans;
    }

};

int main() {
    vector<int> rating{2, 5, 3, 4, 1};
    Solution solution;
    cout << solution.numTeams2(rating) << endl;
    return 0;
}